#ifndef _GRAPH_
#define _GRAPH_

//#include <stdexcept>
#include <iostream>
#include <queue>
using namespace std;

#define INFINITY 256 * 256

class BadVertex {
private:
	int error;
public:
	BadVertex(int num) { error=num; }
	int getBadIndex() const { return error; }
};

template<class T=int, int n=10>
class Graph {
private:
	T adjacentMatrix[(((n+1)*n/2)-n)];
	const int anz;
public:
	Graph(): anz(((n+1)*n/2)-n) { 
		srand ( time(NULL) );
		for(int j=0; j<length(); j++) {
			int random = rand() % 256;
			adjacentMatrix[j] = random;
		}
	}
	int length()  { return anz; }
	int size()  { return n; }
	
	T& operator[](int line) throw(BadVertex)
	{
		if(line < 0 || line >= size)
			throw BadVertex(line);
		else
			return adjacentMatrix[line];
	}
	const T& operator[](int line) const throw(BadVertex)
	{
		if(line < 0 || line >= size)
			throw BadVertex(line);
		else
			return adjacentMatrix[line];
	}			
	
	void insertEdge(int start, int target, int w) throw(BadVertex);
	void display();
	void breadthFirst(int start,int target) throw(BadVertex);
	void dijkstra(int start,int target) throw(BadVertex);
	void depthFirst(int start,int target, T visited[n]) throw(BadVertex);
	int getIndex(int start, int target) throw(BadVertex);
	bool adjacent(int start, int target) throw(BadVertex);
	
};



template<class T, int n>
void Graph<T,n>::insertEdge(int start, int target, int w) throw(BadVertex) {
	if(target<1 || target>n )
		throw BadVertex(target);
	else {
		if(start<1 || start>n )
			throw BadVertex(start);
		else {
			adjacentMatrix[getIndex(start,target)] = w;
		}
	}
}

template<class T, int n>
void Graph<T,n>::display() {
	cout << "\t";
	for(int j=1; j<=size(); j++) {
		cout << "[" << j << "]\t";
	}
	cout << endl << endl;
	for(int j=1; j<=size(); j++) {
		cout << " [" << j << "]\t";
		for(int k=1; k<=size(); k++) {
			if(k!=j) {
				cout << adjacentMatrix[getIndex(j,k)] << "\t";
			}
			else cout << "---\t";
		}
		cout << endl;	
	}
}

template<class T, int n>
void Graph<T,n>::breadthFirst(int start,int target) throw(BadVertex) {
	T visited[size()+1];
	memset(visited, 0, sizeof(visited));
	
	queue<T> queue;
	
	visited[start] = 1;
	printf("%d ", start);
	queue.push(start);
	
	while (! queue.empty()) {
		int p = queue.front();
		queue.pop();
		for(int i= 1; i <= size(); i++){
			if( adjacent(p, i) && visited[i] == 0){
				visited[i] = 1;
				printf("--> %d ", i);
				queue.push(i);
			}
		}
		
	}
}

template<class T, int n>
void Graph<T,n>::depthFirst(int start,int target, T visited[n+1]) throw(BadVertex) {
	visited[start] = 1;
	printf("--> %d  ", start);
	
	for(int i= 1; i <= size(); i++){
		if( adjacent(start, i) && visited[i] == 0 && visited[target] == 0) {
			depthFirst(i, target, visited);	
		}
	}
}

template<class T, int n>
void Graph<T,n>::dijkstra(int start,int target) throw(BadVertex) {
	
	int mini;
	T visited[size()+1];
	T dist[size()+1];
	T way[size()+1];
	memset(visited, 0, sizeof(visited));
	
	if(target<1 || target>n )
		throw BadVertex(target);
	else {
		if(start<1 || start>n )
			throw BadVertex(start);
		else {
			for (int k = 1; k <= size(); k++) {
				dist[k] = INFINITY;
				way[k] = start;	
			}
			dist[start] = 0;
			for (int k = 1; k <= size(); k++) {
				mini = -1;
				for (int i = 1; i <= size(); i++)
					if (!visited[i] && ((mini == -1) || (dist[i] < dist[mini])))
						mini = i;
				visited[mini] = 1;
				
				for (int i = 1; i <= size(); i++) 
					if (adjacent(mini, i)) {
						if (dist[mini] + adjacentMatrix[getIndex(mini, i)] < dist[i]) {
							dist[i] = dist[mini] + adjacentMatrix[getIndex(mini, i)];
							way[i] = mini;
						}
					}
			}
			int count = target;
			do{
				cout << target <<" <--> ";
				target = way[target];
			}
			while(way[target]!=start) ;
			
			if(target!=way[target])
				cout << target <<" <--> " << way[target] << endl;
			else
				cout << target << endl;
		}
	}
}

template<class T, int n>
int Graph<T,n>::getIndex(int start, int target) throw(BadVertex) {
	
	int x,y, index;
	
	if(start<1 || start>size()) 
		throw BadVertex(start);
	else {
		if(target<1 || target>size()) 
			throw BadVertex(target);
		else {	
			if(start<target) {
				x = start;
				y = target;
			}
			else {
				y = start;
				x = target;
			}
			index = 0;
			for(int j=1; j<x; j++)
				index += (n-j-1);
			index += y-2;
			
			return index;
		}	
	}
}

template<class T, int n>
bool Graph<T,n>::adjacent(int start, int target) throw(BadVertex) {
	if(start<1 || start>size()) 
		throw BadVertex(start);
	else {
		if(target<1 || target>size()) 
			throw BadVertex(target);
		else {	
			return adjacentMatrix[getIndex(start, target)] == 0 ? false : true;
		}
	}
}

#endif
